package zcw.com.lib_leet_code;

/**
 * Created by 朱城委 on 2021/8/16.<br><br>
 *
 * 中等：盛最多水的容器
 */
public class Topic11 {

    public static void main(String[] args) {
        Topic11 instance = new Topic11();

        int[] array = new int[] {1,8,6,2,5,4,8,3,7};
        System.out.println(instance.maxArea(array));

        array = new int[] {1,1};
        System.out.println(instance.maxArea(array));

        array = new int[] {4,3,2,1,4};
        System.out.println(instance.maxArea(array));

        array = new int[] {1,2,1};
        System.out.println(instance.maxArea(array));

        array = new int[] {1,0,0,0,0,0,0,2,2};
        System.out.println(instance.maxArea(array));

        array = new int[] {1,8,6,2,5,4,8,25,7};
        System.out.println(instance.maxArea(array));

        array = new int[] {2,3,10,5,7,8,9};
        System.out.println(instance.maxArea(array));

        array = new int[] {1,2,4,3};
        System.out.println(instance.maxArea(array));
    }

    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;

        int area = 0;
        while (left < right) {
            int temp = (right - left) * Math.min(height[right], height[left]);
            if(temp > area) {
                area = temp;
            }

            if(height[left] <= height[right]) {
                int i = left;
                while (height[left] <= height[i] && left < right)
                    left++;
            }
            else {
                int j = right;
                while (height[right] <= height[j] && left < right)
                    right--;
            }
        }

        return area;
    }

    /**
     * 双重循环，超时
     * @param height
     * @return
     */
    public int maxArea2(int[] height) {
        int result = 0;

        for(int i = 0; i < height.length - 1; i++) {
            for(int j = i + 1; j < height.length; j++) {
                int temp = (j - i) * Math.min(height[i], height[j]);
                if(temp > result) {
                    result = temp;
                }
            }
        }

        return result;
    }
}
